package com.vladimirjosu.fhc;

import java.util.ArrayList;
import java.util.Collections;

public class Security {
	private Integer m;
	private ArrayList<String> k2List;
	private ArrayList<String> k1List;

	public Security(String first, String k1, String k2) {
		m = Integer.valueOf(first);
		k1List = new ArrayList<String>();
		k2List = new ArrayList<String>();
		int l = k1.length() / m;
		for (int i = 0; i < m; i++) {
			int a = i * l;
			int b = (i + 1) * l;
			k1List.add(k1.substring(a, b));
			k2List.add(k2.substring(a, b));
		}
		Collections.sort(k2List);
	}

	private String prm(ArrayList<String> k1, int a, ArrayList<String> k2) {
		String s1 = k1.get(a);
		for (int i = 0; i < k2.size(); i++) {
			String s2 = k2.get(i);
			if (isCompat(s1, s2)) {
				k2.remove(i);
				String tmp = merge(s1, s2);
				if (k2.size() > 0) {
					String rez = prm(k1, a + 1, k2);
					if (rez != null) {
						return tmp + rez;
					} else {
						k2.add(i, s2);
					}
				} else {
					return tmp;
				}
			}
		}
		return null;
	}

	public String solve() {
		String solution = "";
		solution = prm(k1List, 0, k2List);
		return solution == null ? "IMPOSSIBLE" : solution;
	}

	private String merge(String s1, String s2) {
		String s = "";
		for (int i = 0; i < s1.length(); i++) {
			char c1 = s1.charAt(i);
			char c2 = s2.charAt(i);
			if (c1 == '?' && c2 == '?') {
				s += 'a';
			} else {
				s += c1 != '?' ? c1 : c2;
			}
		}
		return s;
	}

	private boolean isCompat(String s1, String s2) {
		for (int i = 0; i < s1.length(); i++) {
			char c1 = s1.charAt(i);
			char c2 = s2.charAt(i);
			if (c1 != '?' && c2 != '?' && c1 != c2) {
				return false;
			}
		}
		return true;
	}
}
